package main

/*
	一和零
给你一个二进制字符串数组strs和两个整数m和n 。
请你找出并返回 strs 的最大子集的大小
该子集中 最多 有 m 个 0 和 n 个 1 。

示例 1：
输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。
 */

func findMaxForm(strs []string, m int, n int) int {
	// 构造m*n的矩阵
	arr := make([][]int, m+1)
	for i := 0; i < len(arr); i++ {
		arr[i] = make([]int, n+1)
	}

	for _, str := range strs {
		zero, one := count(str)
		// 用 arr(i, k) 表示使用 i 个 0 和 k 个 1，最多能拼出的字符串数目
		for i := m; i >= zero; i-- {
			for k := n; k >= one; k-- {
				arr[i][k] = Max(1+arr[i-zero][k-one], arr[i][k])
			}
		}
	}

	return arr[m][n]
}

// 统计哪个大
func Max(a, b int) int {
	if a >= b {
		return a
	} else {
		return b
	}
}

// 统计有几个0，几个1
func count(s string) (m, n int) {
	for _, v := range s {
		if string(v) == "0" {
			m += 1
		}
		if string(v) == "1" {
			n += 1
		}
	}
	return m, n
}

func main() {
	
}
